package _mst;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 面试题 01.06. 字符串压缩
 */
public class T0106 {
    public String compressString(String S) {
        StringBuilder ans = new StringBuilder();
        Deque<Character> stack = new LinkedList<>();
        for (char c : (S + "_").toCharArray()) {
            int curSum = 0;
            char curChar = 0;
            while (!stack.isEmpty() && stack.peek() != c) {
                curChar = stack.pop();
                curSum++;
            }
            if (curSum != 0) ans.append(curChar).append(curSum);
            stack.push(c);
        }
        return ans.length() < S.length() ? ans.toString() : S;
    }
}
